#include "header.h"

int quick_sort(int a[1024][1024], int first, int last, int index)
{//Recursive quicksort
	int pivot=0;
	if(last>first)
	{
		pivot=partition(a,first,last, index);
			quick_sort(a,first,pivot-1, index);
			quick_sort(a,pivot+1,last, index);
	}
}

int partition(int a[1024][1024], int first, int last, int index)
{
	int i=first;
	int pivot=0;	//First I thought of using two pointers, and a i for the for(); but we'll use just two instead
					//i will point to the last value of the greater than pivot elements
	int smaller=first;	//smaller will point to the beginning of the greater than pivot elements
	int temp=0;
	pivot=a[index][last];
	for(i=first;i<last;i++)//i goes up until i<last, not i<=last because the last value is the pivot
	{
		if(a[index][i]<pivot)	//To change the Ascending, Descending change the <, >
		{
			if(i>smaller)	//if there is a larger than pivot value before the comparing value,
			{				//we switch the first greater than pivot element with the current comparing smaller than pivot element
				temp=a[index][i];
				a[index][i]=a[index][smaller];
				a[index][smaller]=temp;
			}
			smaller++;	//increase the value of the beginning of the greater than pivot elements
		}				//because we switched a smaller than pivot element with the greater than pivot element
	}
	temp=a[index][last];
	a[index][last]=a[index][smaller];
	a[index][smaller]=temp;
	return smaller;
}
